home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / brklyprl.lha / Emulator / fast_copy.c < prev    next >
C/C++ Source or Header  |  1989-04-14  |  9KB  |  330 lines
  1.  
  2. /* Copyright (C) 1988, 1989 Herve' Touati, Aquarius Project, UC Berkeley */
  3.  
  4. /* Copyright Herve' Touati, Aquarius Project, UC Berkeley */
  5.  
  6. #ifdef WITH_GC
  7. #include <stream.h>
  8. #include <sys/types.h>
  9. #include <sys/time.h>
  10. #include <sys/resource.h>
  11. #include "tags.h"
  12. #include "instr.h"
  13. #include "hash_table.h"
  14. #include "string_table.h"
  15. #include "scan.h"
  16. #include "inst_args.h"
  17. #include "inst_table.h"
  18. #include "memory.h"
  19. #include "basics.h"
  20. #include "top_level.h"
  21. #include "gc.h"
  22. #include "mark_copy.h"
  23.  
  24.  /* LOCAL DECLARATIONS */
  25.  
  26. static DownStack FAST_MARK_STACK;
  27. static CopyStack FAST_COPY_STACK;
  28.  
  29.  /* if does not point directly to new space, either it dereferences to */
  30.  /* a pointer to new space that belongs to some living environment, */
  31.  /* that will be traced later on, or to some old environment, which */
  32.  /* modification would then have been trailed. Therefore, there is no */
  33.  /* need to dereference */
  34. void Env::fast_copy()
  35. {
  36. #ifdef WITH_VIRTUAL_BACK
  37.   Cell* y = e + Y1_ENV_OFFSET + already_treated;
  38.   Cell* y0 = e + Y1_ENV_OFFSET + size;
  39.   for (; y < y0; y++) {
  40.     Cell* ptr = y;
  41.     Cell val = *ptr;
  42.     while (get_tag(val) == TAGREF && addr(val) >= E0 && addr(val) != ptr) {
  43.       ptr = addr(val);
  44.       val = *ptr;
  45.     }
  46.     if (get_tag(val) == TAGCONST) continue;
  47.     if (to_new_space(addr(val)))
  48.       copy_from_base(ptr);
  49.   }
  50. #else
  51.   Cell* y = e + Y1_ENV_OFFSET + already_treated;
  52.   Cell* y0 = e + Y1_ENV_OFFSET + size;
  53.   for (; y < y0; y++) {
  54.     if (get_tag(*y) == TAGCONST) continue;
  55.     if (to_new_space(addr(*y)))
  56.     copy_from_base(y);
  57.   }
  58. #endif
  59. }
  60.  
  61.  /* Needs to make sure that no unbound variable is left in registers */
  62. void fast_copy_restore_top_env()
  63. {
  64.   Cell* PreviousE = cellp(E[E_ENV_OFFSET]);
  65.   int arity = instrp(E[P_ENV_OFFSET])->arg2;
  66.   E = PreviousE;
  67.   for (int i = 0; i < arity; i++) {
  68.     X[i] = deref(E[Y1_ENV_OFFSET + i]);
  69.     if (X[i] == make_ptr(TAGREF, &E[Y1_ENV_OFFSET + i])) {
  70.       Cell new_var = make_ptr(TAGREF, FAST_COPY_STACK.top());
  71.       FAST_COPY_STACK.push(new_var);
  72.       X[i] = E[Y1_ENV_OFFSET + i] = new_var;
  73.     }
  74.   }
  75. }
  76.  
  77.  /* CHOICE POINTS */
  78.  
  79. void setup_cps_fast_copy()
  80. {
  81.  /* treat the case of the cps such that B.h == HMIN now */
  82.   Cell* b = B2 = B;
  83.   while (cellp(b[H_CP_OFFSET]) == HMIN) {
  84.     b[H_CP_OFFSET] = cell(H2);
  85.     b += FIXED_CP_SIZE + b[SIZE_CP_OFFSET];
  86.   }
  87.  
  88.  /* creates a topmost choice point */
  89.   B -= FIXED_CP_SIZE;
  90.   B[E_CP_OFFSET] = cell(E);
  91.   B[H_CP_OFFSET] = cell(H);
  92.   B[TR_CP_OFFSET] = cell(TR);
  93.   B[P_CP_OFFSET] = 0; /* unused */
  94.   B[SIZE_CP_OFFSET] = 0;
  95.  
  96.  /* set B2 to be above E2, TR2 as well; save previous contents */
  97.   SAVED_CP.tr = cellp(B2[TR_CP_OFFSET]);
  98.   SAVED_CP.e = cellp(B2[E_CP_OFFSET]);
  99.   SAVED_CP.h = cellp(B2[H_CP_OFFSET]);
  100.   TR2 = min(TR2, SAVED_CP.tr);
  101.   E2 = max(E2, SAVED_CP.e);
  102.   B2[TR_CP_OFFSET] = cell(TR2);
  103.   B2[E_CP_OFFSET] = cell(E2);
  104.   B2[H_CP_OFFSET] = cell(HMIN);
  105. }
  106.  
  107. void restore_cps_fast_copy()
  108. {
  109.  /* restore B2 to its initial contents */
  110.   B2[TR_CP_OFFSET] = cell(SAVED_CP.tr);
  111.   B2[E_CP_OFFSET] = cell(SAVED_CP.e);
  112.   B2[H_CP_OFFSET] = cell(SAVED_CP.h);
  113.  
  114.  /* compute the new values of H, H2, TR, TR2, E2 */
  115.   H = HMIN;
  116.   H2 = FAST_COPY_STACK.top();
  117.   TR = TR2 = cellp(B[TR_CP_OFFSET]);
  118.   E2 = E;
  119.  
  120.  /* remove the dummy topmost choice point */
  121.   B += FIXED_CP_SIZE;
  122. }
  123.  
  124.  /* takes advantage of the fact that the tag bit is in the lower bits */
  125. void fast_copy_trail_1()
  126. {
  127.   register Cell* tr0 = cellp(B[TR_CP_OFFSET]);
  128.   register Cell* tr = cellp(B2[TR_CP_OFFSET]);
  129.   register Cell* copy_tr = tr;
  130.   register Cell* h = cellp(B2[H_CP_OFFSET]);
  131.   register Cell* e = cellp(B2[E_CP_OFFSET]);
  132.   for (; tr > tr0; tr--) {
  133.     if (cellp(*tr) < h || (cellp(*tr) < e && cellp(*tr) >= E0))
  134.       *copy_tr-- = *tr;
  135.   }
  136.   B[TR_CP_OFFSET] = cell(copy_tr);
  137. }
  138.  
  139. void fast_copy_trail_2()
  140. {
  141.   register Cell* tr0 = cellp(B[TR_CP_OFFSET]);
  142.   register Cell* tr = cellp(B2[TR_CP_OFFSET]);
  143.   for (; tr > tr0; tr--) {
  144.     register Cell* ptr = addr(*tr);
  145.     if (ptr >= E2 || (ptr < E0 && ptr >= HMIN))
  146.       continue;
  147.     if (pointer_to_new(*ptr))
  148.       copy_from_base(ptr);
  149.   }
  150. }
  151.  
  152. void fast_copy_trail()
  153. {
  154.   fast_copy_trail_1();
  155.   fast_copy_trail_2();
  156. }
  157.  
  158.  /* control stacks */
  159.  
  160.  /* we do the traversal of the environment stack and the choice point */
  161.  /* stack together. that way we can avoid having to traverse the */
  162.  /* records twice, and we do not have to use marking nor any extra */
  163.  /* space: just two extra structures. */
  164.  /* will be quite easy to add virtual backtracking inside this routine */
  165.  /* it works as follows: first visit all envs above the topmost choice */
  166.  /* point. then visit all envs that are above the next living env. two */
  167.  /* loops alternating, one visiting next living envs, one visiting the */
  168.  /* next preserved envs. if a given env is shared, its living part is */
  169.  /* first entirely marked, then we wait until the last choice point */
  170.  /* that preserved that env and mark the part that is preserved. */ 
  171.  
  172. void fast_copy_control()
  173. {
  174.  /* only living objects in that case */
  175.   Env env(E);
  176.   for (;;) {
  177.     if (env.e <= E2) {
  178.       if (env.e == E2)
  179.     env.fast_copy();
  180.       break;
  181.     }
  182.     env.fast_copy();
  183.     env.next();
  184.   }
  185. }
  186.  
  187.  /* we save and later restore the topmost entry in the COPY_STACK at */
  188.  /* the time this routine is called. This is to simplify the algorithm */
  189.  /* and avoid copying many times. Here, the main difficulty is the */
  190.  /* correct treatment of refs. Since the order does not matter any */
  191.  /* more here, we can be even a bit more efficient. Each time we */
  192.  /* encounter a ref, we dereference it. If we get a constant, we just */
  193.  /* copy the constant into the origin. If we get an unbound variable, */
  194.  /* we rebind it backwards, and set the original pointer to unbound. */
  195.  /* This may create pointers from new to base space for a while, so we */
  196.  /* should be careful. The idea is to always dereference fully, no */
  197.  /* matter what, and look at where the result is. Only stop when */
  198.  /* marked. Using the FAST_MARK_STACK helps a lot, though it cannot be */
  199.  /* deeper than one element. */
  200.  
  201. void copy_from_base(Cell* p)
  202. {
  203.   FAST_MARK_STACK.init(B);
  204.   FAST_MARK_STACK.push(p);
  205.   for (;;) {
  206.     Cell* var;
  207.     if (FAST_COPY_STACK.nonempty())
  208.       var = FAST_COPY_STACK.pop();
  209.     else if (FAST_MARK_STACK.nonempty())
  210.       var = FAST_MARK_STACK.pop();
  211.     else
  212.       break;
  213.  
  214.     switch (get_tag(*var)) {
  215.     case TAGCONST:
  216.       break;
  217.     case TAGREF: 
  218.       {
  219.     Cell* ptr = addr(*var);
  220.     if (ptr < HMIN || ptr >= E0) {
  221.       if (*var == *ptr) {
  222.         if (ptr > var)
  223.           *ptr = *var = make_ptr(TAGREF, var);
  224.       } else {
  225.         *var = *ptr;
  226.         FAST_MARK_STACK.push(var);
  227.       }
  228.     } else if (marked(ptr)) {
  229.       *var = make_ptr(TAGREF, reloc_addr(ptr));
  230.     } else if (*var == *ptr) {
  231.       *ptr = *var = make_ptr(TAGREF, var);
  232.     } else {
  233.       *var = *ptr;
  234.       FAST_MARK_STACK.push(var);
  235.     }
  236.       }
  237.       break;
  238.     case TAGLIST:
  239.       {
  240.     Cell* list = addr(*var);
  241.     if (list >= HMIN) {
  242.       if (marked(list)) {
  243.         *var = make_ptr(TAGLIST, reloc_addr(list));
  244.       } else {
  245.         *var = make_ptr(TAGLIST, FAST_COPY_STACK.top());
  246.         for (int i = 0; i < 2; i++) {
  247.           mark(list + i);
  248.           Cell* dest = FAST_COPY_STACK.top();
  249.           FAST_COPY_STACK.push(list[i]);
  250.           set_reloc_addr(list + i, dest);
  251.         }
  252.       }
  253.     }
  254.       }
  255.       break;
  256.     case TAGSTRUCT:
  257.       {
  258.     Cell* str = addr(*var);
  259.     if (str >= HMIN) {
  260.       if (marked(str)) {
  261.         *var = make_ptr(TAGSTRUCT, reloc_addr(str));
  262.       } else {
  263.         *var = make_ptr(TAGSTRUCT, FAST_COPY_STACK.top());
  264.         int i0 = get_int(str[1]) + 2;
  265.         for (int i = 0; i < i0; i++) {
  266.           mark(str + i);
  267.           Cell* dest = FAST_COPY_STACK.top();
  268.           FAST_COPY_STACK.push(str[i]);
  269.           set_reloc_addr(str + i, dest);
  270.         }
  271.       }
  272.     }
  273.       }
  274.       break;
  275.     }
  276.   }
  277. }
  278.  
  279.  /* Basic Initializations */
  280. void fast_copy_gc_init()
  281. {
  282. #ifdef WITH_VIRTUAL_BACK
  283.   MARK = 2 * ((GC_COUNTER % 127) + 1); /* values from 2 to 254 */
  284. #else
  285.   MARK = (GC_COUNTER % 255) + 1;       /* values from 1 to 255 */
  286. #endif
  287.   GC_COUNTER++;
  288.   FAST_COPY_STACK.init(H2);
  289. }
  290.  
  291.  /* Collect some data */
  292.  /* some basic data: mark(scan,recovered), copy(scan,recovered), cputime */
  293.  /* the data are given in number of cells, milliseconds. */
  294.  
  295. void fast_copy_stats()
  296. {
  297.   gc_scanned += H_entry_value - HMIN;
  298.   gc_copy_scanned += H_entry_value - HMIN;
  299.   gc_survivors += H2 - H2_entry_value;
  300.   tr_scanned += TR2_entry_value - TR_entry_value;
  301.   tr_survivors += TR2_entry_value - TR;
  302.   if (DISPLAY_GC) {
  303.     cout << "gc(";
  304.     display_stat1("copy", H_entry_value - HMIN, H2 - H2_entry_value);
  305.     display_stat1("tr", TR2_entry_value-TR_entry_value, TR2_entry_value-TR);
  306.   }
  307. }
  308.  
  309.  /* top level */
  310.  /* assumes that GC_DOES_COPY. Should also work if everything is above */
  311.  /* the topmost choice point, though slower than the special purpose */
  312.  /* fast_copy garbage collector */
  313.  
  314. void fast_copy()
  315. {
  316.   init_stats();
  317.   store_regs_in_env();
  318.   setup_cps_fast_copy();
  319.   fast_copy_gc_init();
  320.   init_marking_table();
  321.   fast_copy_trail();
  322.   fast_copy_control();
  323.   fast_copy_restore_top_env();
  324.   restore_cps_fast_copy();
  325.   fast_copy_stats();
  326.   compute_stats();
  327. }
  328.  
  329. #endif
  330.